def strlist(s):
    temp = ''
    l = []
    for i in range(0,len(s)):
        if s[i] != ' ':
            temp += s[i]
        else:
            l.append(temp)
            temp = ''
    l.append(temp)
    return l[:]

def inp():
    t = int(input())
    n_l = []
    data_l = []
    for i in range (0,t):
        n = int(input())
        n_l.append(n)
        data = input()
        data = strlist(data)
        data_l.append(data)
    return t,n_l[:],data_l[:]

def strint(l):
    for i in range(0,len(l)):
        l[i] = int(l[i])

def sort(data_l):
    for i in range(0,len(data_l)):
        data_l[i].sort()
        
def do(data,left_l,right_l,time,run):
#    left_l = data[:]
#    right_l = []
    print('kfk',data,left_l,right_l,time)
    s = 0
    if run == False:
        return
    while True:
        if len(left_l) == 3:
            do(data,[],data[:],time + data[0] + data[1] + data[2],run)
            run = False
            return
        if len(left_l) == 2:
            do(data,[],data[:],time + data[1],run)
            run = False
            return
        if len(left_l) == 1:
            do(data,[],data[:],time + data[0],run)
            run = False
            return
        if len(left_l) == 0:
            run = False
            return
        time1 = data[-2] + data[0] + data[-1] + data[0]
        time2 = data[1] + data[0] + data[-1] + data[1]
        temp = [left_l[-2],left_l[-1]]
        for i in temp:
            left_l.remove(i)
            right_l.append(i)
        do(data,left_l,right_l,time + min(time1,time2),run)
        
        
        
def main():
    t,n_l,data_l = inp()
    print(data_l)
    for i in range(0,len(data_l)):
        strint(data_l[i])
    sort(data_l)
    print(data_l)
    for i in data_l:
        time = 0
        left_l = i[:]
        right_l = []
        do(i,left_l,right_l,time,True)
        print(time)
        
main()
